package com.LeeCode;

import java.util.Arrays;

/**
 * 长度可被 K 整除的子数组的最大元素和
 */

public class Code3381 {
    public static void main(String[] args) {
        int[] nums = {-5, 1, 2, -3, 4};
        int k = 2;
        System.out.println(new Code3381().maxSubarraySum(nums, k));
    }

    public long maxSubarraySum(int[] nums, int k) {
        int n = nums.length;
        long ans = Long.MIN_VALUE, preSum = 0;
        long[] cnt = new long[k];
        Arrays.fill(cnt, Long.MAX_VALUE);
        cnt[0] = 0;
        for (int i = 0; i < n; i++) {
            preSum += nums[i];

            int target = (i + 1) % k;
            if (cnt[target] != Long.MAX_VALUE) {
                ans = Math.max(ans, preSum - cnt[target]);
            }
            cnt[target] = Math.min(cnt[target], preSum);
        }

        return ans;
    }
}
